/*
    SUSAN® - Sole of Unix Save ANything

   

   
*/
/*
 * SUSAN doubly linked list routines.
 *
 * dlist is a doubly linked list with the links being in the list data item.
 *
 * Kern Sibbald, July MMIII
 */

#include "include/susan.h"
#include "lib/dlist.h"


/**
 * Init dlist
 */
void dlist::init(void* item, dlink* link)
{
  head = tail = NULL;
  loffset = (int)((char*)link - (char*)item);
  if (loffset < 0 || loffset > 5000) {
    Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
  }
  num_items = 0;
}

/*
 * Append an item to the list
 */
void dlist::append(void* item)
{
  SetNext(item, NULL);
  SetPrev(item, tail);
  if (tail) { SetNext(tail, item); }
  tail = item;
  if (head == NULL) { /* if empty list, */
    head = item;      /* item is head as well */
  }
  num_items++;
}

/*
 * Prepend an item to the list
 */
void dlist::prepend(void* item)
{
  SetNext(item, head);
  SetPrev(item, NULL);
  if (head) { SetPrev(head, item); }
  head = item;
  if (tail == NULL) { /* if empty list, */
    tail = item;      /* item is tail too */
  }
  num_items++;
}

void dlist::InsertBefore(void* item, void* where)
{
  dlink* where_link = get_link(where);

  SetNext(item, where);
  SetPrev(item, where_link->prev);

  if (where_link->prev) { SetNext(where_link->prev, item); }
  where_link->prev = item;
  if (head == where) { head = item; }
  num_items++;
}

void dlist::InsertAfter(void* item, void* where)
{
  dlink* where_link = get_link(where);

  SetNext(item, where_link->next);
  SetPrev(item, where);

  if (where_link->next) { SetPrev(where_link->next, item); }
  where_link->next = item;
  if (tail == where) { tail = item; }
  num_items++;
}

/*
 *  Insert an item in the list, but only if it is unique
 *  otherwise, the item is returned non inserted
 *
 * Returns: item         if item inserted
 *          other_item   if same value already exists (item not inserted)
 */
void* dlist::binary_insert(void* item, int compare(void* item1, void* item2))
{
  int comp;
  int low, high, cur;
  void* cur_item;

  if (num_items == 0) {
    // Dmsg0(000, "Append first.\n");
    append(item);
    return item;
  }
  if (num_items == 1) {
    comp = compare(item, first());
    if (comp < 0) {
      prepend(item);
      // Dmsg0(000, "Insert before first.\n");
      return item;
    } else if (comp > 0) {
      InsertAfter(item, first());
      // Dmsg0(000, "Insert after first.\n");
      return item;
    } else {
      // Dmsg0(000, "Same as first.\n");
      return first();
    }
  }
  /* Check against last item */
  comp = compare(item, last());
  if (comp > 0) {
    append(item);
    // Dmsg0(000, "Appended item.\n");
    return item;
  } else if (comp == 0) {
    // Dmsg0(000, "Same as last.\n");
    return last();
  }
  /* Check against first item */
  comp = compare(item, first());
  if (comp < 0) {
    prepend(item);
    // Dmsg0(000, "Inserted item before.\n");
    return item;
  } else if (comp == 0) {
    // Dmsg0(000, "Same as first.\n");
    return first();
  }
  if (num_items == 2) {
    InsertAfter(item, first());
    // Dmsg0(000, "Inserted item after.\n");
    return item;
  }
  low = 1;
  high = num_items;
  cur = 1;
  cur_item = first();
  while (low < high) {
    int nxt;
    nxt = (low + high) / 2;
    while (nxt > cur) {
      cur_item = next(cur_item);
      cur++;
    }
    while (nxt < cur) {
      cur_item = prev(cur_item);
      cur--;
    }
    // Dmsg1(000, "Compare item to %d\n", cur);
    comp = compare(item, cur_item);
    // Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
    if (comp < 0) {
      high = cur;
      // Dmsg2(000, "set high; low=%d high=%d\n", low, high);
    } else if (comp > 0) {
      low = cur + 1;
      // Dmsg2(000, "set low; low=%d high=%d\n", low, high);
    } else {
      // Dmsg1(000, "Same as item %d\n", cur);
      return cur_item;
    }
  }
  if (high == cur) {
    InsertBefore(item, cur_item);
    // Dmsg1(000, "Insert before item %d\n", cur);
  } else {
    InsertAfter(item, cur_item);
    // Dmsg1(000, "Insert after item %d\n", cur);
  }
  return item;
}

/*
 *  Insert an item in the list, regardless if it is unique
 *  or not.
 */
void dlist::BinaryInsertMultiple(void* item,
                                 int compare(void* item1, void* item2))
{
  void* ins_item = binary_insert(item, compare);
  /* If identical, insert after the one found */
  if (ins_item != item) { InsertAfter(item, ins_item); }
}

/*
 * Search for item
 */
void* dlist::binary_search(void* item, int compare(void* item1, void* item2))
{
  int comp;
  int low, high, cur;
  void* cur_item;


  if (num_items == 0) { return NULL; }
  cur_item = first();
  if (num_items == 1) {
    comp = compare(item, cur_item);
    if (comp == 0) {
      return cur_item;
    } else {
      return NULL;
    }
  }
  low = 1;
  high = num_items;
  cur = 1;
  cur_item = first();
  while (low < high) {
    int nxt;
    nxt = (low + high) / 2;
    /* Now get cur pointing to nxt */
    while (nxt > cur) {
      cur_item = next(cur_item);
      cur++;
    }
    while (nxt < cur) {
      cur_item = prev(cur_item);
      cur--;
    }
    comp = compare(item, cur_item);
    // Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
    if (comp < 0) {
      high = cur;
      // Dmsg2(000, "set high; low=%d high=%d\n", low, high);
    } else if (comp > 0) {
      low = cur + 1;
      // Dmsg2(000, "set low; low=%d high=%d\n", low, high);
    } else {
      return cur_item;
    }
  }
  /*
   * low == high can only happen if low just
   *   got incremented from cur, and we have
   *   not yet tested cur+1
   */
  if (low == high) {
    cur_item = next(cur_item);
    comp = compare(item, cur_item);
    if (comp == 0) { return cur_item; }
  }
  return NULL;
}


void dlist::remove(void* item)
{
  void* xitem;
  dlink* ilink = get_link(item); /* item's link */
  if (item == head) {
    head = ilink->next;
    if (head) { SetPrev(head, NULL); }
    if (item == tail) { tail = ilink->prev; }
  } else if (item == tail) {
    tail = ilink->prev;
    if (tail) { SetNext(tail, NULL); }
  } else {
    xitem = ilink->next;
    SetPrev(xitem, ilink->prev);
    xitem = ilink->prev;
    SetNext(xitem, ilink->next);
  }
  num_items--;
  if (num_items == 0) { head = tail = NULL; }
}

void* dlist::next(void* item)
{
  if (item == NULL) { return head; }
  return get_next(item);
}

void* dlist::prev(void* item)
{
  if (item == NULL) { return tail; }
  return get_prev(item);
}


/* Destroy the list contents */
void dlist::destroy()
{
  for (void* n = head; n;) {
    void* ni = get_next(n);
    free(n);
    n = ni;
  }
  num_items = 0;
  head = tail = NULL;
}

/* String helpers for dlist usage */

dlistString* new_dlistString(const char* str)
{
  return new_dlistString(str, strlen(str));
}

dlistString* new_dlistString(const char* str, int len)
{
  dlistString* node;
  node = (dlistString*)malloc(sizeof(dlink) + len + 1);
  bstrncpy(node->c_str(), str, len + 1);
  return node;
}
